/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reserveList(ListNode* head)
    {
        ListNode* pre = NULL;
        ListNode* next = head->next;

        while(head) {
            next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    void reorderList(ListNode* head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* right;
        if(!head || !head->next || !head->next->next) {
            return;
        }

        while(fast) {
            fast = fast->next;
            if(fast) {
                fast = fast->next;
                slow = slow->next;
            }
        }
        right = slow->next;
        slow->next = NULL;

        right = reserveList(right);
        slow = head;
        while(right) {
            fast = right->next;
            right->next = slow->next;
            slow->next = right;
            slow = right->next;
            right = fast;
        }
    }
};
